import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PathSum {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return Collections.EMPTY_LIST;
        process(root, targetSum);
        return ans;
    }

    public void process(TreeNode node, int target) {
        if (node.left == null && node.right == null) {
            if (target - node.val == 0) {
                list.add(node.val);
                ans.add(new ArrayList<>(list));
                list.remove(list.size() - 1);
            }
            return;
        }
        if (node.left != null) {
            list.add(node.val);
            process(node.left, target - node.val);
            list.remove(list.size() - 1);
        }
        if (node.right != null) {
            list.add(node.val);
            process(node.right, target - node.val);
            list.remove(list.size() - 1);
        }
    }
}
